/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include "stdio.h"
#include "time.h"
using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
	
	rootPid = -1;
	treeHeight=-1;
	
	treePath = NULL;
	
		
    
}
BTreeIndex::~BTreeIndex()
{
	if(treePath != NULL)
		free(treePath);
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	 RC rc;
	 
     if((rc = pf.open(indexname, mode)) < 0){
		 return rc;
	 }
	 //read existing tree information block
	  if(pf.endPid()> 0){
			char buf[PageFile::PAGE_SIZE];
			int * ibuf= (int *) buf;
			
			pf.read(0, buf);
			
			setHeightAndRoot(ibuf[0],ibuf[1]);
	  }
	  //create a new tree information block
	  else 
	  {
			setHeightAndRoot(treeHeight, rootPid);
	  }
     
     return rc;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	
    return pf.close();
}





void BTreeIndex::insertNonLeafNodeHelper(int height, PageId curr_pid, int in_key, PageId in_pid)
{
	BTNonLeafNode insertInto;
	
	insertInto.read(curr_pid, pf);
	if(insertInto.insert(in_key, in_pid) == RC_NODE_FULL){
			PageId siblingId = pf.endPid();
			BTNonLeafNode siblingNode;
			int midKey;
			//split the non-leaf node
			insertInto.insertAndSplit(in_key, in_pid, siblingNode,  midKey);
		
			insertInto.write(curr_pid, pf);
			siblingNode.write(siblingId, pf);
			
			if(height > 0){
				PageId parent;
				parent = treePath[height-1];
				
				insertNonLeafNodeHelper(height-1, parent, midKey, siblingId);
			}
			else {
				PageId newRootId;
				BTNonLeafNode newRootNode;
				
				newRootId = pf.endPid();
				newRootNode.initializeRoot(curr_pid , midKey, siblingId);
				newRootNode.write(newRootId, pf);
				
				//Increase Height
				setHeightAndRoot(treeHeight+1, newRootId);
				
				
			}
	}
	else{
			
			insertInto.write(curr_pid, pf);
			
	}

}
void BTreeIndex::insertLeafNodeHelper(PageId curr_pid, int in_key, RecordId in_rid)
{
	BTLeafNode insertInto;
	
	//read the leaf node
	insertInto.read(curr_pid, pf);
	//attempt to insert into the leaf.
	if(insertInto.insert(in_key, in_rid) == RC_NODE_FULL){
		PageId oldSibId;
		PageId newSibId;
		BTLeafNode siblingNode;
		int sibKey;
		int parent = treePath[treeHeight-1];
		
		
		//split the node, adding the new keys into the clean node.
		oldSibId = insertInto.getNextNodePtr();
		newSibId = pf.endPid();
		//insert and split the node
		insertInto.insertAndSplit(in_key, in_rid, siblingNode,  sibKey);
		//set original node to point to sibling, sibling to point to old sibling.
		insertInto.setNextNodePtr(newSibId);
		siblingNode.setNextNodePtr(oldSibId);
		
		insertInto.write(curr_pid, pf);
		siblingNode.write(newSibId, pf);
		
		if(treeHeight > 0){
				
				insertNonLeafNodeHelper(treeHeight-1, parent, sibKey, newSibId);
		}
		else {
			PageId newRootId;
			BTNonLeafNode newRootNode;
			
			newRootId = pf.endPid();
			newRootNode.initializeRoot(curr_pid , sibKey, newSibId);
			newRootNode.write(newRootId, pf);
			
			//Increase Height
			setHeightAndRoot(treeHeight+1, newRootId);
			
			
		}
		
	}
	else{
		insertInto.write(curr_pid, pf);
	}



}

RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	rc=0;
	/*SPECIAL CASE: NO TREE, INSERTING ROOT NODE
	 * 
	 */
	if(treeHeight == -1){
		setHeightAndRoot(0, pf.endPid()+1);
	}
	IndexCursor myIndex;
	BTLeafNode insertInto;
	rc = locate(key, myIndex);
	insertLeafNodeHelper(myIndex.pid, key, rid);
	return rc;
	
}


/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the lcation of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
 
IndexCursor BTreeIndex::locateHelper(int searchKey, PageId pid, int height){
	
		//record the current page to the list of pages
		
		
		if(height < treeHeight){
			BTNonLeafNode nonLeafNode;
			nonLeafNode.read(pid, pf);
			treePath[height] = pid;
			nonLeafNode.locateChildPtr(searchKey, pid);
			if(pid < 0){
				IndexCursor idxCursor;
				idxCursor.pid = -1;
				idxCursor.eid = -1;
				return idxCursor;
			}
			
			return locateHelper(searchKey, pid, height+1);
		}
		else{
			BTLeafNode leafNode;
			IndexCursor indexCursor;
			
			indexCursor.pid = pid;
			indexCursor.eid=0;
			
			leafNode.read(pid, pf);
			
			leafNode.locate(searchKey, indexCursor.eid);
			
			return indexCursor;
		}

}
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if(rootPid >= 0){
		cursor= locateHelper(searchKey, rootPid, 0);
		if(cursor.pid >=0)
			return 0;
		else
		{
			fprintf(stdout,"ERROR: Could not locate node (%d,%d). Height is %d.\n", cursor.pid, cursor.eid, treeHeight);
			exit(0);
			//return -1;
		}
		
	}
	else 
		return RC_END_OF_TREE ;
		
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	RC rc=0;
	if(cursor.pid >= pf.endPid()){
		fprintf(stderr, "ERROR: Cannot read key pair; page id out of bounds\n");
		return RC_INVALID_CURSOR ;
	}
	BTLeafNode myLeaf;
	if((rc=myLeaf.read(cursor.pid, pf)) < 0)
		return RC_INVALID_CURSOR;
	
	
	//if the entry is invalid.
	if((rc=myLeaf.readEntry(cursor.eid, key, rid)) < 0){
		return RC_INVALID_CURSOR;
	}
		
	if(cursor.eid +1 < myLeaf.getKeyCount())
		cursor.eid++;
	else
	{
		cursor.eid = 0;
		cursor.pid = myLeaf.getNextNodePtr();
	}
    return 0;
}

void BTreeIndex::setHeightAndRoot(int newHeight, PageId newRoot){
	
		
		if(newHeight >1)
			free(treePath);
			
		treePath = (PageId *) malloc(sizeof(PageId)*(newHeight));
		rootPid = newRoot;
		treeHeight = newHeight;
		
		char buf[PageFile::PAGE_SIZE];
		int * ibuf= (int *) buf;
		ibuf[0] = treeHeight;
		ibuf[1] = rootPid;
		
		pf.write(0, buf);
}

void BTreeIndex::printTreeHelper(PageId pid, int height, bool printLeaves){
		if(height < treeHeight)
		{
				BTNonLeafNode node;
				node.read(pid, pf);
				fprintf(stdout,"NONLEAF===[pid=%d, height=%d]\n", pid, height);
				node.print(true);
				for(int i=0; i < node.getKeyCount()+1; i++){
					node.getPid(i,pid);
					printTreeHelper(pid, height+1, printLeaves);
				}
		}
		else if(printLeaves)
		{
				BTLeafNode node;
				node.read(pid, pf);
				fprintf(stdout,"LEAF===[pid=%d, height=%d]\n", pid, height);
				node.print(true);
			
		}
}
void BTreeIndex::printTree(){
	printTreeHelper(rootPid, 0, true);
	
}


